//-----------------------------------------------------------
//  Purpose:    Check braces in C++ program
//  Author:     John Gauch
//-----------------------------------------------------------
#include "stack3/stack3.h"
#include <cstdlib> 
#include <string>
using namespace std;

//-----------------------------------------------------------
// Check that braces are balanced in C++ program
//-----------------------------------------------------------
bool check_braces()
{
   const char L_BRACE = '{';
   const char R_BRACE = '}';
   Stack stack;
   char ch;

   // Read input until EOF
   while (cin >> ch)
   {
      // Push brace onto stack
      if (ch == L_BRACE)
      {
         if (stack.IsFull()) return false;
	 stack.Push(ch);
      }

      // Pop brace from stack
      else if (ch == R_BRACE)
      {
         if (stack.IsEmpty()) return false;
         if (stack.Top() != L_BRACE) return false;
         ch = stack.Pop();
      }
   }

   // Check stack is empty at end
   return stack.IsEmpty();
}

//-----------------------------------------------------------
// Main program.
//-----------------------------------------------------------
int main()
{
   if (check_braces())
      cout << "Braces are balanced" << endl;
   else
      cout << "Braces are NOT balanced" << endl;
   return 0;
}